/*
 * @lc app=leetcode.cn id=658 lang=golang
 * @lcpr version=30119
 *
 * [658] 找到 K 个最接近的元素
 */

// @lcpr-template-start
package main

import "fmt"

func main() {
	arr := []int{1, 5, 10}
	fmt.Println(findClosestElements(arr, 1, 4))
}

// @lcpr-template-end
// @lc code=start
func findClosestElements(arr []int, k int, x int) []int {
	itarget := binarySearch(arr, x, 0, len(arr)-1)

	l := max(itarget-k-1, 0)
	r := min(itarget+k+1, len(arr))
	for r-l > k {
		if abs(arr[l]-x) <= abs(arr[r-1]-x) {
			r--
		} else {
			l++
		}
	}
	return arr[l:r]
}

func binarySearch(arr []int, x int, left int, right int) int {
	if x <= arr[0] {
		return 0
	} else if x >= arr[len(arr)-1] {
		return len(arr) - 1
	}
	for left < right {
		mid := left + (right-left)/2
		if arr[mid] == x {
			return mid
		} else if arr[mid] < x {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

// @lc code=end

/*
// @lcpr case=start
// [1,2,3,4,5]\n4\n3\n
// @lcpr case=end

// @lcpr case=start
// [1,2,3,4,5]\n4\n-1\n
// @lcpr case=end

*/
